package leetcode_900;

/**
 *@author 周杨 
 *ExpressiveWords_809 判断字符串能否通过一定规则压缩成另外一个字符串
 *describe:用遍历方式解决 AC 9%
 *2018年10月26日 上午11:23:27
 */
public class ExpressiveWords_809 {
	 public int expressiveWords(String S, String[] words) {
	        int count = 0;
	        String s=convert(S);
	        for (String word : words) {
	            if (canExtend(word, s)) count++;
	        }
	        return count;
	    }
	    private boolean canExtend(String word, String s) {
			// check if the word can extend to S
	        String w = convert(word);
	        if (w.length() != s.length()) return false;
	        for (int i = 0; i < w.length(); i++) {
	            if (Character.isDigit(w.charAt(i))) {
	                if (s.charAt(i) < w.charAt(i)) {
	                    return false;
	                } else if (s.charAt(i) == w.charAt(i)) {
	                    continue;
	                } else if ((int) s.charAt(i) - '0' < 3) {
	                    return false;
	                }
	            } else {
	                if (w.charAt(i) != s.charAt(i)) {
	                    return false;
	                }
	            }
	        }
	        return true;
	    }
	    private String convert(String s) {
	        int l = 0;
	        int r = 0;
	        StringBuilder sb = new StringBuilder();
	        while (l < s.length() && r < s.length()) {
	            while (r < s.length() && s.charAt(r) == s.charAt(l)) {
	                r++;
	            }
	            sb.append(s.charAt(l));
	            sb.append(r - l);
	            l = r;
	        }
	        return sb.toString();
	    }
}
